/**
 * 二分法大全
 */
public class BinarySearch {

    /**
     * 数组重复值中最右侧的索引
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0,j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }

        }
        return candidate;
    }

    /**
     * 数组重复值中最右侧的索引
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m; // 记录候选位置
                i = m + 1;	   // 继续向右
            }
        }
        return candidate;
    }

    /**
     * 遍历重复数组最左侧索引
     * @param a
     * @param target
     * @return 若无则返回插入点
     */
    public static int binarySearchLeftmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    /**
     * 遍历重复数组最右侧索引
     * @param a
     * @param target
     * @return 若无则返回前任
     */
    public static int binarySearchRightmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i - 1;
    }

    public static int binaryRecursionSearch(int[] a, int target) {
        return recursion(a, target, 0, a.length - 1);
    }

    private static int recursion(int[] a, int target, int i, int j) {
        if (i > j) {
            return -1;
        }
        int m = (i + j) >>> 1;
        if (a[m] < target) {
            return recursion(a, target, m + 1, j);
        } else if (target < a[m]) {
            return recursion(a, target, i, m - 1);
        }else {
            return m;
        }
    }
}
